The present invention relates generally to the field of circuit analysis, and more particularly to the determination of critical parts and component correlations in a circuit.
With growing system complexities and circuit scaling, circuit sensitivity checks are becoming more challenging and more important when analyzing issues such as, for example, device variation, yield, and reliability. Typically, system sensitivity checks are performed by testing circuit components one-by-one in simulators, which can cause problems when considering technology scaling.
System checks may be performed to find critical parts (e.g., components or grouping of components within a circuit) to better understand how components work together when different workloads are applied to the circuit. Process variation and yield become challenging in Scaled CMOS technology (less than 14 nm technology nodes). New transistor technology (e.g., CNT, III-V, PCM) tends to be more sensitive to process and result in larger variations.
Centrality is a known theory discussed in a number of scholarly articles including: Borgatti, Stephen P. (2005). “Centrality and Network Flow” and Bonacich, Phillip (1987). “Power and Centrality: A Family of Measures”. Centrality is used in graph theory and network analysis using indicators of centrality to identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin. Centrality indices indicate what characterizes an important vertex and is given in terms of a real-valued function on the vertices of the graph. Each vertex can be given a rank which identifies the most important nodes in the graph.
Centrality characterization by network flows, a network can be considered a description of the paths along which something flows. The path of flow allows a characterization based on the type of flow and the type of path encoded by the centrality. A flow can be based on transfers, where each indivisible item goes from one node to another, like a package delivery which goes from the delivery site to a client's house. A second case is the serial duplication, where this is a replication of the item which goes to the next node. The last case is the parallel duplication, with the item being duplicated to several links at the same time, like a radio broadcast which provides the same information to many listeners at once, (or as applicable to an embodiment in the present invention, signals that are sent to multiple nodes such as multiple components in a circuit).
With regards to centrality characterization by walk structure, an alternative classification can be derived from how the centrality is constructed. This can be split into two classes. Centralities are either Radial or Medial. Radial centralities count walks which start/end from the given vertex. When centralities are categorized by their approach to cohesiveness, it becomes apparent that the majority of centralities inhabit one category. The count of the number of walks starting from a given vertex differs only in how walks are defined and counted. Restricting consideration to this group allows for a soft characterization which places centralities on a spectrum from walks of length one (degree centrality) to infinite walks (eigenvalue centrality). The degree and eigenvalue centralities are examples of radial centralities, counting the number of walks of length one or length infinity. Medial centralities count walks which pass through the given vertex. The canonical example is Freeman's betweenness centrality, the number of shortest paths which pass through the given vertex.
Centrality indices have two important limitations, one obvious and the other subtle. The obvious limitation is that a centrality which is optimal for one application is often sub-optimal for a different application. Indeed, if this were not so, we would not need so many different centralities. The more subtle limitation is the commonly held fallacy that vertex centrality indicates the relative importance of vertices. Centrality indices are explicitly designed to produce a ranking which allows indication of the most important vertices. The error is two-fold. Firstly, a ranking only orders vertices by importance; it does not quantify the difference in importance between different levels of the ranking. This may be mitigated by applying Freeman centralization to the centrality measure in question, which provide some insight to the importance of nodes depending on the differences of their centralization scores. Furthermore, Freeman centralization enables one to compare several networks by comparing their highest centralization scores.